//螺旋矩阵

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        for (int i = 0; i < m; i++) {
            reverse(matrix[i].begin(), matrix[i].end());
        }
        for (int i = 0; i < m - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                swap(matrix[i][j], matrix[m - j - 1][n - i - 1]);
            }
        }
    }
};

//腐烂的橘子
class Solution {
public:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    typedef pair<int, int> PII;
    int orangesRotting(vector<vector<int>>& grid) {
        int size = 0;
        int ret = 0;

        int m = grid.size();
        int n = grid[0].size();
        // vector<vector<bool>>vis;
        queue<PII> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    q.push({i, j});
                } else if (grid[i][j] == 1) {
                    size++;
                }
            }
        }
        if (!size && q.empty())
            return 0;

        while (q.size()) {
            int sz = q.size();
            ret++;
            for (int j = 0; j < sz; j++) {
                auto [a, b] = q.front();
                q.pop();
                // ret++;
                for (int i = 0; i < 4; i++) {
                    int x = dx[i] + a;
                    int y = dy[i] + b;
                    if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                        q.push({x, y});
                        grid[x][y] = 2;
                        size--;
                    }
                }
            }
        }
        if (size)
            return -1;
        return ret - 1;
    }
};